/*
实验8-1 城市间紧急救援
分数 25
作者 陈越
单位 浙江大学

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。
输入格式:

输入第一行给出 4 个正整数 n、m、s、d，其中
n（2≤n≤500）是城市的个数，顺便假设城市的编号为 0 ~ (n−1)；m 是快速道路的条数；s
是出发地的城市编号；d是目的地的城市编号。

第二行给出 n 个正整数，其中第 i 个数是第 i
个城市的救援队的数目，数字间以空格分隔。随后的 m
行中，每行给出一条快速道路的信息，分别是：城市 1、城市
2、快速道路的长度，中间用空格分开，数字均为整数且不超过
500。输入保证救援可行且最优解唯一。 输出格式:

第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从 s 到 d
的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。 输入样例:

4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2

输出样例:

2 60
0 1 3
*/

/*
两个测试没通过：
1）	5条不同的最短路
3）	最大N和M，随机数据构成完全图
*/

#include "../base/MGraph.cpp"

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>

using namespace std;

// 定义权重的最大值
#define MaxWeight 0x7FFF

// 定义权重结构体
struct Weight {
    int energy; // 道路的长度
    int value;  // 目标点救援队的数目

    Weight(int e = 0, int v = 0) : energy(e), value(v) {}

    bool operator==(const Weight& other) {
        return energy == other.energy && value == other.value;
    }

    bool operator!=(const Weight& other) {
        return energy != other.energy || value != other.value;
    }
    // 重载加法运算符
    Weight operator+(const Weight& other) const {
        return Weight(energy + other.energy, value + other.value);
    }

    // 重载比较运算符
    bool operator>(const Weight& other) const {
        if (energy == other.energy) return value < other.value;
        return energy > other.energy;
    }

    // 重载比较运算符
    bool operator<(const Weight& other) const {
        if (energy == other.energy) return value > other.value;
        return energy < other.energy;
    }
};

// Dijkstra 算法
void Dijkstra(const MGraph<int, Weight> &graph, vector<Weight>& weight, vector<int>& path, int start) {
    int num_vertex = graph.get_num_vertex();
    vector<bool> visited(num_vertex, false);
    weight.resize(num_vertex, Weight(MaxWeight, 0));
    weight[start] = Weight(0, 0);

    path.resize(num_vertex, -1);
    for (int i = 0; i < num_vertex; ++i) {
        if (graph.has_edge(start, i)) {
            path[i] = start;
        }
    }

    priority_queue<pair<Weight, int>, vector<pair<Weight, int>>, greater<pair<Weight, int>>> pq;
    pq.push({weight[start], start});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (visited[u]) continue;
        visited[u] = true;

        for (int v = 0; v < num_vertex; ++v) {
            if (graph.has_edge(u, v)) {
                Weight new_weight = weight[u] + graph.get_edge(u, v);
                if (new_weight < weight[v]) {
                    weight[v] = new_weight;
                    pq.push({weight[v], v});
                    path[v] = u;
                }
            }
        }
    }
}

int main() {
    int n, m, s, d;
    cin >> n >> m >> s >> d;
    MGraph<int, Weight> graph(n, Weight(MaxWeight, 0), true);
    int rescue[n];
    for (int i = 0; i < n; ++i) {
        cin >> rescue[i];
    }
    for (int i = 0; i < m; ++i) {
        int v1, v2, w;
        cin >> v1 >> v2 >> w;
        graph.set_edge(v1, v2, Weight(w, rescue[v2]));
        graph.set_edge(v2, v1, Weight(w, rescue[v1]));
    }
    vector<Weight> weight;
    vector<int> path;

    Dijkstra(graph, weight, path, s);
    
    vector<int> result;
    int max_rescue = rescue[s];
    for (int i = d; i != s; i = path[i]) {
        result.push_back(i);
        max_rescue += rescue[i];
    }
    result.push_back(s);
    reverse(result.begin(), result.end());


    cout << result.size()-1 << " " << max_rescue << endl;
    for (int i = 0; i < result.size(); ++i) {
        if (i != 0) {
            cout << " ";
        }
        cout << result[i];
    }
    return 0;
}